//
//  SearchInsert.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/17.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  35. 搜索插入位置

import UIKit

/*
 35. 搜索插入位置
 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

 你可以假设数组中无重复元素。

 示例 1:

 输入: [1,3,5,6], 5
 输出: 2
 示例 2:

 输入: [1,3,5,6], 2
 输出: 1
 示例 3:

 输入: [1,3,5,6], 7
 输出: 4
 示例 4:

 输入: [1,3,5,6], 0
 输出: 0

 */

class SearchInsert: NSObject {
    //二分法
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        if nums.count == 0 {
            return 0
        }
        
        var left = 0
        var right = nums.count-1
        
        //var ans = 0
        
        while left <= right {
            let midIndex = left + (right - left)/2
            //let midIndex = (left + right)/2
            
            //let midIndex = left + (right - left)/2 + 1  在此题中不正确
            
            
            let midNum = nums[midIndex]
            
            if midNum < target{
                //中间数小于目标值 往右边找
                left = midIndex + 1
            }else if midNum == target{
                //中间数等于目标值 直接返回索引
                return midIndex
            }else{
                //中间数大于于目标值 往左边找
                right = midIndex - 1
            }
        }
        
        return left
    }
}
